/*
题目: 最大公因数等于 K 的子数组数目
给你一个整数数组 nums 和一个整数 k ，请你统计并返回 nums 的子数组中元素的最大公因数等于 k 的子数组数目。

子数组 是数组中一个连续的非空序列。

数组的最大公因数 是能整除数组中所有元素的最大整数。

https://leetcode.cn/problems/number-of-subarrays-with-gcd-equal-to-k
 */
public class SubarrayGCD {
    public int subarrayGCD(int[] nums, int k) {
        // 暴力, 依次遍历每一个子数组
        int src = 0, n = nums.length;
        for (int i = 0; i < n; i ++) {
            // 如果没有 k 这个因子, 那以 i 为头的子数组就没有贡献值了
            if (nums[i] % k != 0) continue ;
            int g = 0;
            for (int j = i; j < n; j ++) {
                g = gcd(g, nums[j]);
                // 如果 g > K , 还是有可能为 k 的
                if (g == k)
                    src ++;
                if (g < k) { // 但是如果 < k , 那就这个子数组就没有机会了
                    break;
                }
            }
        }

        return src;
    }

    private int gcd(int a, int b) {
        if (a < b) return gcd(b, a);
        while (b > 0) {
            int t = a % b;
            a = b;
            b = t;
        }
        return a;
    }
}
